Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Buy Two Chocolates

Problem statement

You are in a chocolate shop where each chocolate has a price, as listed in an array prices. With a certain amount of money in your pocket, you aim to purchase exactly two chocolates.

You would like to minimize the combined cost of these chocolates so that you are left with as much money as possible, without going into debt.

Calculate the amount of money you'll have left after making the purchase. If it's not possible to buy two chocolates without overspending, return the original amount of money you had.

Examples

Example 1:

  • Input: prices = [2, 5, 3, 9], money = 10
  • Expected Output: 5
  • Justification: The optimal choice is to buy chocolates priced at 2 and 3, costing a total of 5. Therefore, you're left with 10 - 5 = 5.

Example 2:

  • Input: prices = [10, 20, 15, 5, 25, 30, 35, 40], money = 50
  • Expected Output: 35
  • Justification: The cheapest two chocolates has cost 5 and 10. Purchasing these costs 15 in total. Thus, you are left with 50 - 15 = 35.

Example 3:

  • Input: prices = [7, 1, 5, 3], money = 3
  • Expected Output: 3
  • Justification: It's impossible to buy two chocolates without going into debt, so you keep your original amount of 3.

Solution

To solve this problem, we first sort the array of chocolate prices in ascending order. This arrangement allows us to easily identify the two cheapest chocolates, as they will be positioned at the beginning of the sorted array. By purchasing these two chocolates, we ensure that we spend the minimum possible amount of our budget, thereby maximizing the leftover money. Subtracting the total cost of these two chocolates from the initial amount of money provides us with the desired result. This approach is both straightforward and efficient, as it leverages sorting to quickly solve the problem.

Step-by-step Algorithm

  1. Sort the array of chocolate prices in ascending order.
  2. Select the first two elements of the sorted array as they represent the cheapest chocolates.
  3. Calculate the sum of the prices of these two chocolates.
  4. Subtract this sum from the initial amount of money to find the leftover money.
  5. Return the leftover money. If the sum of the prices of the two cheapest chocolates exceeds the initial amount of money, it indicates that it's not possible to buy two chocolates without going into debt; hence, return the original amount of money in such a case.

Algorithm Walkthrough

Given the input prices = [10, 20, 15, 5, 25, 30, 35, 40], money = 50:

  1. Sort the prices array: First, we sort the array of chocolate prices to easily identify the cheapest options. The sorted array becomes [5, 10, 15, 20, 25, 30, 35, 40].

  2. Identify the two cheapest chocolates: The two cheapest chocolates are the first two elements of the sorted array, which are priced at 5 and 10.

  3. Calculate the total cost of these chocolates: We add the prices of these two chocolates together, resulting in a total cost of 5 + 10 = 15.

  4. Determine if the purchase is possible within the budget: Before making the purchase, we need to ensure that the total cost of the two chocolates does not exceed our budget of 50. In this case, 15 is less than 50, which means the purchase is within our budget.

  5. Calculate the leftover money: Since the total cost of 15 is within our budget, we subtract this amount from our initial money to determine how much will be left after the purchase. Therefore, we perform the calculation 50 - 15 = 35.

  6. Return the result: The algorithm returns 35, indicating the amount of money left after buying the two cheapest chocolates from the sorted list.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: due to the sorting step, where n is the number of chocolates (or elements in the array). This is the dominant factor in the time complexity.
  • Space Complexity: for the additional space used (ignoring the space for the input array). This accounts for the constants and minimal extra variables used in the algorithm. If considering the sorting algorithm's space usage, it could be for in-place sorting algorithms like QuickSort due to recursive stack space.
Buy Two Chocolates (easy)
Root Equals Sum of Children (easy)
Mark as Completed

On this page

Problem statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis